package leetcode.top100;

import offerbook.Code51_FindRepeatNumInArray;

/**
 * 给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
 * <p>
 * 示例 1:
 * <p>
 * 输入: [1,3,4,2,2]
 * <p>
 * 输出: 2
 * <p>
 * 示例 2:
 * <p>
 * 输入: [3,1,3,4,2]
 * <p>
 * 输出: 3
 * <p>
 * 说明：
 * <p>
 * 不能更改原数组（假设数组是只读的）。
 * <p>
 * 只能使用额外的 O(1) 的空间。
 * <p>
 * 时间复杂度小于 O(n²) 。
 * <p>
 * 数组中只有一个重复的数字，但它可能不止重复出现一次。
 * <p>
 * 类似题目见{@link Code51_FindRepeatNumInArray}
 *
 * @since 2019/12/17 0017 下午 12:25
 */
public class Code287_FindRepeatNumInArray_寻找重复数字 {


    public int findDuplicate(int[] nums) {
        if(nums == null || nums.length <=1) return -1;
        return process6(nums);
    }


//    方式1：两次循环，时间O(n²),空间O(1)
//    方式2：排序，时间O(nlogN),空间O(1)
//    方式3,4：借助桶或hashSet，时空都是O(n)
    public static int bucketProcess(int[] nums) {
        //len = n+1
        int len = nums.length;
        int[] bucket = new int[len];
        //数字在1-n之间。准备n+1个桶,0,1,...,n号。
        for (int i = 0; i < len; i++) {
            if (bucket[nums[i]] >= 1) return nums[i];
            bucket[nums[i]]++;
        }

        return -1;
    }


    /**
     * 方式5：归位算法，分析见笔记
     * @param nums
     * @return
     */
    private static int process5(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            //当前位置arr[i]!=i,则一直交换，把arr[i]=index与arr[index]交换，
            //直到arr[i]==i,如果index == arr[index],则说明重复
            while (nums[i] != i) {
                int index = nums[i];
                if (index == nums[index]) {
                    return index;
                }
                //否则交换
                swap(nums, index, i);
            }

        }

        //处理nums[0]
        int index = nums[0];
        if (index == nums[index]) return index;
        return -1;
    }

    private static void swap(int[] arr, int i, int j) {
        if(arr[i] == arr[j]) return;
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

    /**
     * 方式6：
     */
    private static int process6(int[] nums){
        if(nums == null || nums.length == 0)return -1;
        //标记法
        for (int i = 0; i < nums.length; i++) {
            int index = Math.abs(nums[i]) ;
            if(nums[index] < 0) return index;
            nums[index] = -nums[index];
        }
        return -1;
    }
}
